#include <bits/stdc++.h>
using namespace std;

// 【题目】力扣377. 组合总和 Ⅳ
// 【难度】中等
// 【提交】2025.10.23 https://leetcode.cn/problems/combination-sum-iv/submissions/673018929/
// 【标签】动态规划；记忆化搜索
class Solution_LC0377 {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> memo(target + 1, -1);
        auto dfs = [&](this auto&& dfs, int i) {
            if (i == 0) return 1;
            int &res = memo[i];
            if (res != -1) return res;
            res = 0;
            for (int x : nums) if (x <= i) res += dfs(i - x);
            return res;
        };
        return dfs(target);
    }
};

/**
 * @brief 学习总结：
 * 本题使用记忆化递归（DFS+Memo）实现，思路清晰直观。
 * 优点：
 * - 记忆化搜索避免了重复计算，时间复杂度为O(target * n)
 * - 递归思路自然，符合组合问题的数学定义
 * 
 * 缺点：
 * - 递归深度可能较大，存在栈溢出风险
 * - 相比迭代DP，常数开销稍大
 * 
 * 改进建议：
 * 可改用迭代DP写法，避免递归开销：
 * 
 * int combinationSum4(vector<int>& nums, int target) {
 *     vector<unsigned long long> dp(target + 1, 0);
 *     dp[0] = 1;
 *     for (int i = 1; i <= target; ++i) {
 *         for (int x : nums) {
 *             if (i >= x) dp[i] += dp[i - x];
 *         }
 *     }
 *     return dp[target];
 * }
 * 
 * 注意：使用unsigned long long防止整数溢出
 */